One of the most common tasks in computer animation is “inverse-kinematics.” Inverse-kinematics (IK) is concerned with the positioning (or “posing”) of animated objects—e.g., determining a joint configuration required to place a particular part of an articulated figure at a particular location in global space. For example, if the figure to be posed is an arm that has an elbow and a wrist, the question of how to orient the wrist and bend the elbow such that the hand is in a particular location is an IK problem. IK is used, for example, in commercial 3D animation packages, motion capture analysis, robot motion planning, and game software, to name a few applications.
Inverse-kinematics is one of the oldest problems in computer animation, tracing its origins back to the problem of positioning industrial robots, A number of techniques have been developed to position an articulated figure. All such techniques reveal a tension between quality and expenditure of resources. Positioning an articulated figure with rotational degrees of freedom (or, for that matter, determining the motion of such a figure) is non-linear and computationally expensive. Thus, the most accurate techniques are often unsuitable for applications where figures must be posed or set in motion in real-time (e.g., a game), and faster algorithms often make use of approximations that, while efficient to compute, make the pose seem less “natural.”
The simplest IK techniques approximate the problem as a linear one. For example, when the change in a figure's position is small (i.e., the starting configuration is near the desired one), iterative linear approximations may be used to compute the position. For more complex motions, however, this simple technique may produce insufficient results.
Other techniques are based on non-linear optimization. These techniques typically have a run-time that is highly dependent on the difficulty of the task; additionally, many of these optimizations make use of a “guess,” so the run-time is also dependent on the quality of the guess. Thus, the amount of time that it takes to solve a given IK problem is unpredictable, which is undesirable in real-time applications. Additionally, many non-linear IK techniques make little use of the large body of human biomechanics knowledge.
Synergy-based IK uses a measure of how much a particular joint contributes to a given IK task (the synergy), in order to reduce the dimensionality of the problem and to help ensure that the results are human-like. This technique, however, in turn relies on complex biomechanical models of how creatures move. Since that body of knowledge does not encode the full gamut of human motions, synergy-based IK cannot fulfill many desired IK tasks.
Example-based IK interpolates a range of poses from discrete examples often generated via motion capture, hand animation, or costly biomechanical simulation. These techniques may produce high-quality poses and may achieve good runtime efficiency; however they suffer from high memory requirements due to the large number of examples required by existing techniques in order to achieve high fidelity, which makes them unattractive for real-world applications. Moreover, existing example-based techniques typically fail to address the fact that an example may have a limited range of influence—that is, an example's relevance in interpolating a pose is diminished, if the parameters of the pose are relatively distant from the parameters of the example.
In view of the foregoing, there is a need for a system and method that combines the real-time, artist-directed quality of example-based techniques and which also overcomes the drawbacks of the prior art.